|
In mathematical optimization, Bland's rule (also known as Bland's algorithm or Bland's anti-cycling rule) is an algorithmic refinement of the simplex method for linear optimization. With Bland's rule, the simplex algorithm solves feasible linear optimization problems without cycling.〔.〕 There are examples of degenerate linear optimization problems on which the original simplex algorithm would cycle forever. Such cycles are avoided by Bland's rule for choosing a column to enter the basis. Bland's rule was developed by Robert G. Bland, now a professor of operations research at Cornell University. ==Algorithm== One uses Bland's rule during an iteration of the simplex method to decide first what column (known as the ''entering variable'') and then row (known as the ''leaving variable'') in the tableau to pivot on. Assuming that the problem is to minimize the objective function, the algorithm is loosely defined as follows: # Choose the lowest-numbered (i.e., leftmost) nonbasic column with a negative (reduced) cost. # Now among the rows choose the one with the lowest ratio between the (transformed) right hand side and the coefficient in the pivot tableau where the coefficient is greater than zero. If the minimum ratio is shared by several rows, choose the row with the lowest-numbered column (variable) basic in it. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bland's rule」の詳細全文を読む スポンサード リンク
|